/*
Date:20210427 23:12PM
key:再一次刷新对递归的认识。
首先要缩小到一个足够小的子结构。像这题的根左右，一共有几种情况。
    根与左，根与右，经过根 三者中的最大刷新最大值。
    注意，返回的时候只能从 根与左，根与右 中挑大的返回，经过根的无法返回。

    一些感慨:其实大部分困难题，最后都是一个一般复杂的子结构。
    或者是一个子状态。考虑清楚子结构的各种可能，再去想与上一层的关系。
 */
class Solution {
public:

    int Sum(TreeNode*root,int&k)
    {
        if(root!=nullptr)
        {
            int le=max(0,Sum(root->left,k));
            int ri=max(0,Sum(root->right,k));
            int root_down_sum=root->val+max(le,ri);
            int tmp=max(root->val+le+ri,root_down_sum);
            k=max(k,tmp);
            
        return root_down_sum;

        }
        else
        {
            return 0;
        }
    }
    int maxPathSum(TreeNode* root) {
        int max=INT_MIN;
        
        Sum(root,max);
        return max;
    }
};